(*~\Глагол\Отделы\Иное~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
(**)                        ОТДЕЛ Ряд;
(*============================================================================*)
(* НАЗНАЧЕНИЕ: упорядочивание рядов и поиск в рядах                           *)
(*============================================================================*)
ИСПОЛЬЗУЕТ
  Набор ИЗ "..\Иное\";
(*
ВИД
            (* предок (опора, база) доступа к любому ВИДу набор *)
  Набор.Доступ-=ДОСТУП К Набор.Вид;
            (* предок (опора, база) любого ВИДа набор *)
  Набор.Вид-=НАБОР КОН; 
*)
ВИД
  Вид-   =НАБОР КОН;     (* опорный вид (абстрактный предок) других НАБОРов *)
  Доступ-=ДОСТУП К Вид;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Упоряд-(ряд+:РЯД ИЗ Доступ; всего:ЦЕЛ;
                                  сравнить:ЗАДАЧА(с1-,с2-:Вид):ЦЕЛ);
(* Быстрое упорядочивание с помощью разделения на участки (Ч.Хоар) *)
ПЕР
  Л,П:ЦЕЛ;        (* текущий участок                   *)
  л,п:ЦЕЛ;        (* новый участок                     *)
  граница:Доступ; (* граничное значение для разделение *)
  рядл:Доступ;    (* промежуточное значение для обмена *)
  глубина:ЦЕЛ;    (* текущая глубина стека             *)
  (* стек для новых участков *)
  стек:РЯД 32 ИЗ НАБОР Л,П:ЦЕЛ КОН; 
УКАЗ
  глубина:=0; 
  стек[глубина].Л:=0; 
  стек[глубина].П:=всего-1;
  ПОВТОРЯТЬ
    (* выбор из стека последнего запроса *)
    Л:=стек[глубина].Л; 
    П:=стек[глубина].П;
    УМЕНЬШИТЬ(глубина);
    ПОВТОРЯТЬ
      (* разделение ряд[Л]...ряд[П] *)
      л:=Л; п:=П;
      граница:=ряд[(Л+П) ДЕЛИТЬ 2];
      ПОВТОРЯТЬ
        ПОКА сравнить(ряд[л]^,граница^) < 0 ВЫП УВЕЛИЧИТЬ(л) КОН;
        ПОКА сравнить(граница^,ряд[п]^) < 0 ВЫП УМЕНЬШИТЬ(п) КОН;
        ЕСЛИ л <= п ТО (* обмен ряд[л] с ряд[п] *)
          рядл:=ряд[л];
          ряд[л]:=ряд[п];
          ряд[п]:=рядл;
          УВЕЛИЧИТЬ(л);
          УМЕНЬШИТЬ(п)
        КОН
      ДО л > п;
      ЕСЛИ п-Л < П-л ТО
        ЕСЛИ л < П ТО (* запись в стек запроса на упорядочивание правой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=л;
          стек[глубина].П:=П
        КОН;
        П:=п (* продолжение упорядочивания левой части *)
      ИНАЧЕ
        ЕСЛИ Л < п ТО (* запись в стек запроса на упорядочивание левой части *)
          УВЕЛИЧИТЬ(глубина);
          стек[глубина].Л:=Л;
          стек[глубина].П:=п
        КОН;
        Л:=л (* продолжение упорядочивания правой части *)
      КОН
    ДО Л >= П
  ДО глубина < 0
КОН Упоряд;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Поиск-(слаг-:Вид;
               ряд+:РЯД ИЗ Доступ; дл:ЦЕЛ; сравнить:ЗАДАЧА(с1-,с2-:Вид):ЦЕЛ):Доступ;
ПЕР
  пол,рез,нач,всего:ЦЕЛ;
УКАЗ
  нач:=0;
  всего:=дл;
  ПОКА всего > 0 ВЫП
    пол:=всего ДЕЛИТЬ 2;
    рез:=сравнить(слаг,ряд[нач+пол]^);
    ЕСЛИ рез <= 0 ТО
      ЕСЛИ рез = 0 ТО 
        ВОЗВРАТ ряд[нач+пол] 
      КОН;
      всего:=пол
    ИНАЧЕ
      УВЕЛИЧИТЬ(нач,пол+1);
      УМЕНЬШИТЬ(всего,пол+1)
    КОН
  КОН;
  ВОЗВРАТ ПУСТО
КОН Поиск;

(*~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~*)
ЗАДАЧА Вставка-(слаг:Доступ;
               ряд+:РЯД ИЗ Доступ; дл+:ЦЕЛ; сравнить:ЗАДАЧА(с1-,с2-:Вид):ЦЕЛ);
ПЕР
  пол,рез,нач,всего:ЦЕЛ;
УКАЗ
  нач:=0;
  всего:=дл;
  КОЛЬЦО
    ЕСЛИ всего <= 0 ТО ВЫХОД КОН;
    пол:=всего ДЕЛИТЬ 2;
    рез:=сравнить(слаг^,ряд[нач+пол]^);
    ЕСЛИ рез <= 0 ТО
      ЕСЛИ рез = 0 ТО ВОЗВРАТ КОН;
      всего:=пол
    ИНАЧЕ
      УВЕЛИЧИТЬ(нач,пол+1);
      УМЕНЬШИТЬ(всего,пол+1)
    КОН
  КОН;
  ЕСЛИ дл=РАЗМЕР(ряд) ТО ВОЗВРАТ КОН;
  всего:=дл;
  ПОКА всего > нач ВЫП
    ряд[всего]:=ряд[всего-1];
    УМЕНЬШИТЬ(всего)
  КОН;
  ряд[нач]:=слаг;
  УВЕЛИЧИТЬ(дл)
КОН Вставка;

КОН Ряд.